0519. 随机翻转矩阵【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - Fisher-Yates 洗牌 + 哈希表

1. 📝 题目描述

• leetcode

给你一个 m x n 的二元矩阵 matrix，且所有值被初始化为 0。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j)，并将它的值变为 1。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j]，并将其对应格子中的值变为 1
• void reset() 将矩阵中所有的值重置为 0

示例：

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

---

提示：

• 1 <= m, n <= 10^4
• 每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
• 最多调用 1000 次 flip 和 reset 方法。

2. 🎯 s.1 - Fisher-Yates 洗牌 + 哈希表

c

#define HASH_SIZE 10007
typedef struct Entry { int key; int val; struct Entry* next; } Entry;

typedef struct {
    int m, n, total;
    Entry* table[HASH_SIZE];
} Solution;

int getOrDefault(Solution* obj, int key) {
    int idx = ((unsigned int)key) % HASH_SIZE;
    for (Entry* e = obj->table[idx]; e; e = e->next)
        if (e->key == key) return e->val;
    return key;
}

void putVal(Solution* obj, int key, int val) {
    int idx = ((unsigned int)key) % HASH_SIZE;
    for (Entry* e = obj->table[idx]; e; e = e->next)
        if (e->key == key) { e->val = val; return; }
    Entry* e = (Entry*)malloc(sizeof(Entry));
    e->key = key; e->val = val; e->next = obj->table[idx]; obj->table[idx] = e;
}

void clearTable(Solution* obj) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry* e = obj->table[i];
        while (e) { Entry* t = e; e = e->next; free(t); }
        obj->table[i] = NULL;
    }
}

Solution* solutionCreate(int m, int n) {
    Solution* obj = (Solution*)calloc(1, sizeof(Solution));
    obj->m = m; obj->n = n; obj->total = m * n;
    return obj;
}

int* solutionFlip(Solution* obj, int* retSize) {
    *retSize = 2;
    int* res = (int*)malloc(sizeof(int) * 2);
    int r = rand() % obj->total;
    obj->total--;
    int val = getOrDefault(obj, r);
    putVal(obj, r, getOrDefault(obj, obj->total));
    res[0] = val / obj->n;
    res[1] = val % obj->n;
    return res;
}

void solutionReset(Solution* obj) {
    obj->total = obj->m * obj->n;
    clearTable(obj);
}

void solutionFree(Solution* obj) {
    clearTable(obj);
    free(obj);
}

js

/**
 * @param {number} m
 * @param {number} n
 */
var Solution = function (m, n) {
  this.m = m
  this.n = n
  this.total = m * n
  this.map = new Map()
}

/**
 * @return {number[]}
 */
Solution.prototype.flip = function () {
  const rand = Math.floor(Math.random() * this.total)
  this.total--
  const val = this.map.get(rand) ?? rand
  this.map.set(rand, this.map.get(this.total) ?? this.total)
  return [Math.floor(val / this.n), val % this.n]
}

Solution.prototype.reset = function () {
  this.total = this.m * this.n
  this.map.clear()
}

py

class Solution:
    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.total = m * n
        self.map = {}

    def flip(self) -> List[int]:
        r = random.randint(0, self.total - 1)
        self.total -= 1
        val = self.map.get(r, r)
        self.map[r] = self.map.get(self.total, self.total)
        return [val // self.n, val % self.n]

    def reset(self) -> None:
        self.total = self.m * self.n
        self.map.clear()

• 时间复杂度：flip $O(1)$，reset $O(F)$，$F$ 为已翻转次数
• 空间复杂度：$O(F)$

算法思路：

• 将矩阵展平为一维，用哈希表实现虚拟交换
• 每次随机选一个位置，与末尾交换，缩小范围